/***************************************************
 * @Author: OBKoro1
 * @Create: 2020-04-08
 * @LastEditors: OBKoro1
 * @LastEditTime: 2020-04-08
 * @FilePath: \leetcode-exercise\279-完全平方数\dp.c
 ****************************************************/

/**
 * 解题方案
 * 思路：
 * 首先初始化长度为n+1的数组dp，每个位置都为0
 * 如果n为0，则结果为0
 * 对数组进行遍历，下标为i，每次都将当前数字先更新为最大的结果，即dp[i]=i，比如i=4，最坏结果为4=1+1+1+1即为4个数字
 * 动态转移方程为：dp[i] = MIN(dp[i], dp[i - j * j] + 1)，i表示当前数字，j*j表示平方数
 * 时间复杂度：O(n*sqrt(n))，sqrt为平方根
 **/
#define MIN(x, y) ((x) < (y) ? (x) : (y))
int numSquares(int n)
{
    int i;
    int j;
    int res;
    if (n <= 0)
    {
        return 0;
    }
    int *dp = (int *)malloc(sizeof(int) * (n + 1));
    /* 都将当前数字先更新为最大的结果,注意取等号 */
    for (i = 0; i <= n; i++)
    {
        dp[i] = i;
    }

    for (i = 1; i <= n; i++)
    {
        /* 注意这里取等号 i - j * j >= 0 */
        for (j = 1; i - j * j >= 0; j++)
        {
            /* debug print */
            printf("dp[%d]: %d dp[%d]:%d\r\n", i, dp[i], (i - j * j), dp[i - j * j]);
            /* 注意动态转移方程 */
            dp[i] = MIN(dp[i], dp[i - j * j] + 1);
        }
    }

    res = dp[n];
    return res;
}